package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.difficulty.DYellow;
import pro.softzhang.algo.flag.knowledge.KBinarySearch;

/**
 * 69. x的平方根 https://leetcode.cn/leetbook/read/binary-search/xe9cog/
 *
 * 核心解法及其变种。
 */
@DYellow
public class LC69_Sqrtx {
    public static void main(String[] args) {
        int x = 8;
        System.out.println(new Solution().mySqrt(x));
    }

    @KBinarySearch
    static
    class Solution {
        public int mySqrt(int x) {
            int left = 1, right = x;
            while (left <= right) {
                int middle = left + (right - left) / 2;
                if(middle <= x / middle) {
                    if((middle + 1) > x / (middle + 1)) {
                        return middle;
                    }
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }
            }
            return 0;
        }
    }
}